package class_06;

import java.util.HashSet;
import java.util.Stack;

import static com.sun.org.apache.xalan.internal.xsltc.compiler.util.Type.Node;

/**
 * dfs
 * @author LOGAN
 *  流程：
    1，利用栈实现
    2，从源节点开始把节点按照深度放入栈，然后弹出
    3，每弹出一个点，把该节点下一个没有进过栈的邻接点放入栈
    4，直到栈变空
 */
public class Code_02_DFS {
	/**
	 * 对一个node进行dfs
	 * @param node
	 */
	public static void dfs(class_06.Node node) {
		if (node == null) {
			return;
		}
		Stack<class_06.Node> stack = new Stack<>();
		HashSet<class_06.Node> set = new HashSet<>();
		stack.add(node);
		set.add(node);
		System.out.println(node.value);
		//stack pop
		while (!stack.isEmpty()) {
			class_06.Node cur = stack.pop();
			for (Node next : cur.nexts) {
				
				if (!set.contains(next)) {
					//stack 放入cur ，和next
					//set  也放入next 
					stack.push(cur);
					stack.push(next);
					set.add(next);
					System.out.println(next.value);
					break;
				}
			}
		}
	}

}
